#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

typedef struct LNode *PtrToNode;
struct LNode 
{
    double data;
    PtrToNode next;
};
typedef PtrToNode List;
typedef PtrToNode Position;

List Insert(List L, double X);
void Display(List L);
void Merge(List A, List B, List &C);

int main()
{
    List example_list_A = NULL, example_list_B = NULL, example_list_C = NULL;

    example_list_A = Insert(example_list_A, 10.0);
    example_list_A = Insert(example_list_A, 5.0);
    example_list_A = Insert(example_list_A, 1.0);
    Display(example_list_A);

    example_list_B = Insert(example_list_B, 12.0);
    example_list_B = Insert(example_list_B, 7.0);
    example_list_B = Insert(example_list_B, 3.0);
    Display(example_list_B);

    Merge(example_list_A, example_list_B, example_list_C);
    Display(example_list_C);
    Display(example_list_A);
    Display(example_list_B);

    return 0;
}

List Insert(List L, double X)
{
    Position new_node;

    new_node = (List)malloc(sizeof(struct LNode));
    new_node->data = X;
    new_node->next = L;
    L = new_node;

    return L;
}

void Display(List L)
{
    for (List tmp = L; tmp != NULL; tmp = tmp->next)
        printf("%lf ", tmp->data);
    printf("\n");
}

void Merge(List A, List B, List &C)
{
    List p = A->next;
    List q = B->next;
    
    if (A->data < B->data)
    {
        q = B;
        C = A;
        C->next = NULL;
    }
    else
    {
        p = A;
        C = B;
        C->next = NULL;
    }
    
    List r;
    r = C;
    
    while (p != NULL && q != NULL)
    {
        if (p->data <= q->data)
        {
            r->next = p;
            p = p->next;
            r = r->next;
        }   else
        {
            r->next = q;
            q = q->next;
            r = r->next;
        }
    }
    r->next = NULL;
    if (p != NULL)
        r->next = p;
    if (q != NULL)
        r->next = q;    
}